//
//  CommonSolution.cpp
//  leetcode
//
//  Created by Ellie on 2021/2/4.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include <stdio.h>

#include "CommonSolution.h"

int CommonSolution::myatoi(string str)
{
    return 10;
}

// 189. 旋转数组
void CommonSolution::reverse(vector<int>& nums, int K)
{
    int length = nums.size();
    K = K % length;
    reverse(nums, 0, length - 1);
    reverse(nums, 0, K - 1);
    reverse(nums, K, length - 1);
}

void CommonSolution::reverse(vector<int>& nums, int start, int end)
{
    while(start < end)
    {
        int temp = nums[start];
        nums[start++] = nums[end];
        nums[end--] = temp;
    }
}

string CommonSolution::addBinary(string a, string b)
{
    int i = a.size() - 1;
    int j = b.size() - 1;
    
    int carry = 0;
    string result = "";
    for(;i>=0 || j >=0 || carry != 0;i--,j--)
    {
        int avalue = i < 0 ? 0 : a[i] - '0';
        int bvalue = j < 0 ? 0 : b[j] - '0';
        
        int value = avalue + bvalue + carry;
        carry = value / 2;
        char ch = value % 2 + '0';
        result.insert(0, 1, ch);
    }
    return result;
}

//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
//进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

// 使用原地哈希方法
// https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
// 将元素按照下标放到指定的位置
// 遍历一次数组把大于等于1的和小于数组大小的值放到原数组对应位置，然后再遍历一次数组查当前下标是否和值对应，如果不对应那这个下标就是答案，否则遍历完都没出现那么答案就是数组长度加1。
// 索引和内容对应
int CommonSolution::firstMissingPositive(vector<int>& nums)
{
    int size = nums.size();
    for(int i =0;i<size;i++)
    {
        // 将数组内容放到相应的位置上
        while(nums[i] > 0 && nums[i] <= size && (nums[i] != nums[nums[i] - 1]))
        {
            // temp - 1 存放的内容 = nums[i]
            int temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp - 1] = temp;
        }
    }
    for(int i=0;i<size;i++)
    {
        if(nums[i] != i + 1)
            return i + 1;
    }
    return size + 1;
}

// 1. 哈希表判断重复
// 2. 排序判断相邻元素是否相同
// 3. 快慢指针，将数组构建成链表通过找到环的起点就是答案

//给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
//假设 nums 只有 一个重复的整数 ，找出 这个重复的数

int CommonSolution::findDuplicate(vector<int>& nums)
{
    int size = nums.size();
    for(int i=0;i<size;i++)
    {
        // must be while!!!
        while(nums[i] != i + 1)
        {
            if(nums[i] == nums[nums[i] - 1])
            {
                return nums[i];
            }
            int temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp - 1] = temp;
        }
    }
    return -1;
}

// 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
// 找到所有出现两次的元素。
// 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
// 原地标记方法，出现两次和出现一次，只会有这两种情况
// 同一个索引点是否被访问过
vector<int> CommonSolution::findDuplicates(vector<int>& nums)
{
    int size = nums.size();
    vector<int> result;
    for(int i=0;i<size;i++)
    {
        int index = abs(nums[i] - 1);
        if(nums[index] < 0)
        {
            result.push_back(abs(nums[i]));
        }
        nums[index] = nums[index] * -1;
    }
    return result;
}

int CommonSolution::findRepeatNumber(vector<int>& nums)
{
//    // Normal HashMap
//    int size = nums.size();
//    unordered_map<int, int> hashmap;
//    for(int i=0;i<size;i++){
//        if(hashmap.find(nums[i]) != hashmap.end())
//            return nums[i];
//        else
//            hashmap[nums[i]] = 1;
//    }
//    return 0;
    
    // 0~N-1 存放到数组
    // 将数组按照0到N-1存放到数组中
    int size = nums.size();
    int temp = 0;
    for(int i=0;i<size;i++)
    {
        while(nums[i] != i)
        {
            if(nums[i] == nums[nums[i]])
                return nums[i];
            
            temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
    }
    return -1;
}

vector<int> CommonSolution::findDisappearedNumbers(vector<int>& nums)
{
    vector<int> result;
    int size = nums.size();
    for(int i=0;i<size;i++)
    {
        int index = nums[i] - 1;
        nums[index] = -abs(nums[index]);
    }
    for(int i=0;i<size;i++)
    {
        if(nums[i] > 0)
            result.push_back(i + 1);
    }
    return result;
}

// 输入：s = "ADOBECODEBANC", t = "ABC"
// 输出："BANC"
string CommonSolution::minWindow(string s, string t)
{
    int size = s.size();
    unordered_map<int, int> window;
    unordered_map<int, int> need;
    for(auto & ch : t)
    {
        need[ch] ++;
    }
    // result start
    int startleft = 0;
    // min len
    int len = INT_MAX;
    
    int left = 0;
    int right = 0;
    
    int valid = 0;
    
    while(right < size)
    {
        char ch = s[right];
        if(need.count(ch))
        {
            window[ch] ++;
            if(window[ch] == need[ch])
                valid ++;
        }
        right ++;
        
        while(need.size() == valid)
        {
            if(right - left < len)
            {
                startleft = left;
                len = right - left;
            }
            ch = s[left];
            if(need.count(ch))
            {
                if(window[ch] == need[ch])
                    valid --;
                window[ch] --;
            }
            left ++;
        }
    }
    return len == INT_MAX ? "" : s.substr(startleft, len);
}

// check s2 include s1
// 如何只包含小写的字母，可以用vector26存放26个英文字母 index = ch - 'a';
bool CommonSolution::checkInclusion(string s1, string s2)
{
    int n = s1.length();
    int m = s2.length();
    
    if(m < n)
        return false;
    vector<int> cnt1(26);
    vector<int> cnt2(26);
    
    for(int i=0;i<n;i++)
    {
        cnt1[s1[i] - 'a'] ++;
        cnt2[s2[i] - 'a'] ++;
    }
    
    if(cnt1 == cnt2)
        return true;
    for(int i=n;i<m;i++)
    {
        cnt2[s2[i] - 'a']++;
        cnt2[s2[i - n] - 'a']--;
        if(cnt2 == cnt1)
            return true;
    }
    return false;
}

// check s2 include s1
// 输入为小写字母，可以直接用vector保存26个字母
bool CommonSolution::checkInclusionTwo(string s1, string s2)
{
    if(s2.length() < s1.length())
        return false;
    int size = s2.size();
    
    int left = 0;
    int right = 0;
    
    unordered_map<int, int> window;
    unordered_map<int, int> need;
    // set need
    for(auto & ch : s1)
    {
        need[ch] ++;
    }
    // check if window is valid
    int valid = 0;
    while(right < size)
    {
        // extend window
        char ch = s2[right];
        right ++;
        if(need.count(ch))
        {
            window[ch] ++;
            if(window[ch] == need[ch])
            {
                valid++;
            }
        }
        
        // check if we need shrink window
        // 排除不满足的字符left
        while(right - left >= s1.size())
        {
            if(valid == need.size())
                return true;
            ch = s2[left];
            left ++;
            if(need.count(ch))
            {
                if(window[ch] == need[ch])
                    valid --;
                window[ch] --;
            }
        }
    }
    return false;
}

// 3. 无重复字符的最长子串
int CommonSolution::lengthOfLongestSubstring(string s)
{
    int size = s.size();
    if(size < 2)
        return size;
    
    int left = 0;
    int right = 0;
    int len = INT_MIN;
    
    unordered_map<int, int> window;
    
    while(right < size)
    {
        char ch = s[right];
        right ++;
        window[ch] ++;
        
        while(window[ch] > 1)
        {
            char dd = s[left];
            window[dd] --;
            left ++;
        }
        len = max(len, right - left);
    }
    return len;
}

// 209. 长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。输入的为正整数，没哟负数则可以考虑使用滑动窗口
// 正整数决定，前缀和一定是递增的，可以使用记录前缀和+二分查找的方法解决问题，NLogN的复杂度

// 滑动窗口复杂度为LogN
int CommonSolution::minSubArrayLen(int target, vector<int>& nums)
{
    int size = nums.size();
    if(size == 0)
        return 0;
    else if(nums[0] != target && size == 1)
        return 0;

    int result = INT_MAX;
    int sum = 0;
    int right = 0;
    int left = 0;
    while(right < size)
    {
        int num = nums[right];
        sum += num;
        right ++;

        while(sum >= target)
        {
            int minus = right - left;
            if(result > minus)
            {
                result = minus;
            }
            sum -= nums[left];
            left ++;
        }
    }
    return result == INT_MAX ? 0 : result;
}


// 整体窗口滑动
// 28. 实现 strStr()
int CommonSolution::strStr(string haystack, string needle)
{
    if(needle[0] == '\0')
        return 0;
    int hsize = haystack.length();
    int nsize = needle.length();
    
    // <= is the key.
    for(int i=0;i <= hsize-nsize;i++)
    {
        int j = 0;
        for(;j<nsize;j++)
        {
            if(haystack[i + j] != needle[j])
            {
                break;
            }
        }
        
        if(j == nsize)
            return i;
    }
    return -1;
}

// 718. 最长重复子数组 可以使用DP方法解答，也可以使用滑动窗口
// 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 A在B+B在A中滑动得到的结果才是解

int CommonSolution::findLength(vector<int>& A, vector<int>& B)
{
    // DP
    int m = A.size();
    int n = B.size();

    if(m == 0 || n == 0)
        return 0;
    vector<vector<int>>dptable = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
    // dptable[i][j]:表示i，j公共的最长子数组的长度
    int result = INT_MIN;
    for(int i=1;i<=m;i++)
    {
        int j = 1;
        for(;j<=n;j++)
        {
            if(A[i-1] == B[j-1])
                dptable[i][j] = dptable[i-1][j-1] + 1;
            else
                dptable[i][j] = 0;

            if(result < dptable[i][j])
                result = dptable[i][j];
        }
    }
    return result == INT_MIN ? 0 : result;
}

int CommonSolution::findLengthSlideWindow(vector<int>& A, vector<int>& B)
{
    int n = A.size(), m = B.size();
    int ret = 0;
    for (int i = 0; i < n; i++) {
        int len = min(m, n - i);
        int maxlen = maxLength(A, B, i, 0, len);
        ret = max(ret, maxlen);
    }
    for (int i = 0; i < m; i++) {
        int len = min(n, m - i);
        int maxlen = maxLength(A, B, 0, i, len);
        ret = max(ret, maxlen);
    }
    return ret;
}

int CommonSolution::maxLength(vector<int>& A, vector<int>& B, int addA, int addB, int len)
{
    int ret = 0, k = 0;
    for (int i = 0; i < len; i++) {
        if (A[addA + i] == B[addB + i]) {
            k++;
        } else {
            k = 0;
        }
        ret = max(ret, k);
    }
    return ret;
}

// 9. 回文数
// 翻转只比较一半的数字，前提是排除了负数+结尾为0的数字
// Beware of overflow when you reverse the integer. 只比较一半，除以10去除各位，%10获取个位数
// 转换成字符串比较是否相等，比较低效
bool CommonSolution::isPalindrome(int x)
{
    if(x < 0)
        return false;
    if(x % 10 == 0 && x != 0)
        return false;
    
    int result = 0;
    while(x > result)
    {
        result = result * 10 + (x % 10);
        x = x / 10;
    }
    // 奇数和偶数问题
    return x == result || result / 10 == x;
}

// 7. 整数反转,假设环境不允许存储 64 位整数（有符号或无符号）,注意溢出的问题
// 如何判断溢出问题，INT_MIN，INT_MAX
int CommonSolution::reverse(int x)
{
    int result = 0;
    
    // result * 10 + x % 10 > INT_MAX
    // result * 10 + x % 10 < INT_MIN
    int maxlast = INT_MAX % 10; // 7
    int minlast = INT_MIN % 10; // -8
    
    while(x != 0)
    {
        if(result > INT_MAX / 10 || (result == INT_MAX / 10 && x % 10 > maxlast))
            return 0;
        if(result < INT_MIN / 10 || (result == INT_MIN / 10 && x % 10 < minlast))
            return 0;
        result = result * 10 + x % 10;
        x /= 10;
    }
    return result;
}


// 下一个排列
// https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
void CommonSolution::nextPermutation(vector<int>& nums)
{
    int size = nums.size();
    int firstIndex = 0;
    int secondIndex = 0;
    
    // 1. find largest K nums[K] < nums[K+1]
    for(int i = size - 1;i>0;i--)
    {
        if(nums[i] > nums[i-1])
        {
            firstIndex = i - 1;
            secondIndex = i;
            break;
        }
    }
    // Check if can find K, If Can't find K and K+1 just reverse to base ascend order
    if(firstIndex == secondIndex)
    {
        std::reverse(nums.begin(), nums.end());
        return;
    }
    // 2. find largest J nums[J] > nums[K]
    int thirdIndex = size - 1;
    for(int i = size - 1;i>=0;i--)
    {
        if(nums[i] > nums[firstIndex])
        {
            thirdIndex = i;
            break;
        }
    }
    // 3. swap nums[J] &&  nums[K]
    swap(nums[thirdIndex], nums[firstIndex]);
    // 4. reverse [K+1, n] K+1~last element
    std::reverse(nums.begin() + secondIndex, nums.end());
}

vector<int> CommonSolution::twoSum(vector<int>& nums, int target)
{
//    int low = 0;
//    int high = nums.size();
//
//    sort(nums.begin(), nums.end());
//    while(low < high)
//    {
//        int sum = nums[low] + nums[high];
//        if(sum > target)
//            high --;
//        else if(sum < target)
//            low ++;
//        else
//            return vector<int>{nums[low], nums[high]};
//    }
//    return vector<int>{-1,-1};
    
    unordered_map<int, int> table;
    for(int i=0;i<nums.size();i++)
    {
        int value = target - nums[i];
        if(table.find(value) != table.end())
            return vector<int>{i, table[value]};
        table[nums[i]] = i;
    }
    return vector<int>{-1,-1};
}

vector<vector<int>> CommonSolution::threeSum(vector<int>& nums)
{
    vector<vector<int>> result;
    int size = nums.size();
    if(size < 3)
        return result;
    
    int left = 0;
    int right = size - 1;
    sort(nums.begin(), nums.end());

    for(int i=0;i<size - 2;i++)
    {
        if(nums[i] > 0)
            break;
        if(i > 0 && nums[i] == nums[i-1])
            continue;
        left = i + 1;
        right = size - 1;
        vector<int> track;
        while(left < right)
        {
            int sum = nums[i] + nums[left] + nums[right];
            if(sum == 0)
            {
                track = vector<int>{nums[i], nums[left], nums[right]};
                result.push_back(track);
                
                left ++;
                right --;
                while(left < right && nums[left] == nums[left - 1])
                    left ++;
                while(left < right && nums[right] == nums[right + 1])
                    right --;
            }
            else if( sum < 0)
            {
                left ++;
            }
            else if(sum > 0)
            {
                right --;
            }
        }
    }
    return result;
}

// 560. 和为K的子数组
int CommonSolution::subarraySum(vector<int>& nums, int k)
{
    // prefix sum just count
    int size = nums.size();
    int result = 0;
    // s[i] : index i presum.
    // s[i,j] == k 区间
    // s[j] - s[i] == k need check result
    // s[i] = s[j] - k need check s[i]
    unordered_map<int, int> table;
    table[0] = 1;
    int sum = 0;
    for(int i=0;i<size;i++)
    {
        sum += nums[i];
        int checksum = sum - k;
        result += table[checksum];
        table[sum]++;
    }
    return result;
}

int CommonSolution::numSubarrayProductLessThanK(vector<int>& nums, int k)
{
    int size = nums.size();
    int left = 0;
    int right = 0;
    int product = 1;
    int result = 0;
    // 更新窗口的条件是窗口的数据元素乘积>=k
    // 缩小窗口
    // [5,2,6]
    // left index = 5
    // right index = 6
    // [5,2,6],[2,6],[6] = right - left + 1;
    while(right < size)
    {
        product *= nums[right];
        right ++;
        while(product >= k && left < right)
        {
            product /= nums[left++];
        }
        result += (right - left);
    }
    return result;
}

// 152. 乘积最大子数组
// 负数的存在会将最大变成最小，最小变成最大，我们需要一次操作得到较大的结果
// 遇到负数做一次最大值和最小值的交换，更新最大值和最小值，同时根据最大值更新结果
int CommonSolution::maxProduct(vector<int>& nums)
{
    int size = nums.size();
    int maxproduct = 1;
    int minproduct = 1;
    int result = INT_MIN;
    // 需要维护一个最大值和最小值
    // 因为存在负数，会将最大值变成最小值，最小值变成最大的值
    // 如果是负数则进行交换，保证这次的乘积将结果变大，一直需要变大
    for(int i=0;i<size;i++)
    {
        if(nums[i] < 0)
            swap(maxproduct, minproduct);
        maxproduct = max(nums[i], nums[i] * maxproduct);
        minproduct = min(nums[i], nums[i] * minproduct);
        
        result = max(maxproduct, result);
    }
    
    return result;
}

// 69. x 的平方根
int CommonSolution::mySqrt(int x)
{
    int high = x;
    int low = 0;
    int result = 1;
    long long longresult = 0;
    
    while(low <= high)
    {
        int mid = (high - low) / 2 + low;
        longresult = (long long)mid * mid;
        if(longresult <= x)
        {
            low = mid + 1 ;
            result = mid;
        }
        else
        {
            high = mid - 1;
        }
    }
    return result;
}


// 50. Pow(x, n)
double CommonSolution::myPow(double x, int n)
{
    if(n >= 0)
        return myPowRecursion(x, n);
    else
        return 1.0 / myPowRecursion(x, n);
}

// 举例子，3的5次方，3的3次方，3的2次方
double CommonSolution::myPowRecursion(double x, int n)
{
    if( n == 0)
        return 1.0;
    double result = myPow(x, n / 2);
    if(n % 2 == 0)
        return result * result;
    else
        return result * result * x;
}

vector<int> CommonSolution::spiralOrder(vector<vector<int>>& matrix)
{
    // row
    int m = matrix.size();
    // column
    int n = matrix[0].size();
    
    int top = 0;
    int bottom = m - 1;
    int left = 0;
    int right = n - 1;
    
    vector<int> result;
    //[left->right]
    //[top-bottom]
    //[right-left]
    //[bottom-top]
    while(true)
    {
        for(int i = left;i <= right;i++)
        {
            result.push_back(matrix[top][i]);
        }
        top ++;
        if(top > bottom)
            break;
        
        for(int j = top;j<=bottom;j++)
        {
            result.push_back(matrix[j][right]);
        }
        right --;

        if(left > right)
            break;

        for(int i=right;i>=left;i--)
        {
            result.push_back(matrix[bottom][i]);
        }
        bottom --;
        if(top > bottom)
            break;
        
        for(int j=bottom;j>= top;j--)
        {
            result.push_back(matrix[j][left]);
        }
        left ++;
        if(left > right)
            break;
    }
    return result;
}

// 矩阵的转置
vector<vector<int>> CommonSolution::transposedMatrix(vector<vector<int>>& matrix)
{
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> result(n, vector<int>(m));
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            result[j][i] = matrix[i][j];
        }
    }
    return result;
}

// "3[a]2[bc]" -> "aaabcbc"
// "2[abc]3[cd]ef" -> "abcabccdcdcdef"
// "abc3[cd]xyz" -> "abccdcdcdxyz"
// "30[a2[cd4[c]]]"
// 4[c] -> 2[cdccccc] -> 30[acdccccacdcccc]

// [作为分割 数字+字母的分界线
// 操作参数为：字符串+数字
// 进行的操作为字符串拼接
// ]作为一次计算开始

// 字符串涉及到数字处理的别忘记大于等于10的数字
string CommonSolution::decodeString(string s)
{
    int size = s.size();
    stack<string> stringsk;
    stack<int> numssk;
    
    string curstr = "";
    string result = "";
    
    int num = 0;
    int i = 0;
    while(i < size)
    {
        if(isdigit(s[i]))
        {
            num = num * 10 + (s[i] - '0');
        }
        else if(isalpha(s[i]))
        {
            curstr += s[i];
        }
        else if(s[i] == '[')
        {
            numssk.push(num);
            num = 0;
            stringsk.push(curstr);
            curstr = "";
        }
        if(s[i] == ']')
        {
            int count = numssk.top();
            numssk.pop();
            for(int i=0;i<count;i++)
            {
                stringsk.top() += curstr;
            }
            curstr = stringsk.top();
            stringsk.pop();
        }
        i++;
    }
    result += curstr;
    return result;
}


// 224. 基本计算器
// 输入：s = "(1+(4+5+2)-3)+(6+8)"
// 输出：23
int CommonSolution::calculateHard(string s)
{
    int size = s.size();
    stack<int> sk;
    int prefix = 1;
    int calresult = 0;
    int num = 0;
    for(int i=0;i<size;i++)
    {
        if(isdigit(s[i]))
        {
            num = num * 10 + (s[i] - '0');
        }
        else if(s[i] == ' ')
            continue;
        else if(s[i] == '(')
        {
            //push pre-calresult
            sk.push(calresult);
            // push prefix
            sk.push(prefix);
            num = 0;
            prefix = 1;
            calresult = 0;
        }
        else if(s[i] == ')')
        {
            calresult += prefix * num;
            // * prefix
            calresult *= sk.top(); sk.pop();
            // + pre-calresult
            calresult += sk.top(); sk.pop();
            num = 0;
        }
        else
        {
            // '+','-'
            calresult += (prefix * num);
            if(s[i] == '+')
                prefix = 1;
            else if(s[i] == '-')
                prefix = -1;
            num = 0;
        }
    }
    return calresult + prefix * num;
}

// 输入: "3+2*2"
// 输出: 7
int CommonSolution::calculateMedium(string s)
{
    int size = s.size();
    int num = 0;
    stack<int> nums;
    char op = '+';
    // 保证最后一个num被加入到计算
    for(int i=0;i<=size;i++)
    {
        if(s[i] == ' ')
            continue;
        if(isdigit(s[i]))
        {
            num = num * 10 + (s[i] - '0');
        }
        else
        {
            switch (op) {
                case '+':
                    nums.push(num);
                    break;
                case '-':
                    nums.push(num);
                    break;
                case '*':
                    nums.top() *= num;
                    break;
                case '/':
                    nums.top() /= num;
                    break;
                default:
                    break;
            }
            op = s[i];
            num = 0;
        }
    }
    // add all nums
    int result = 0;
    while(!nums.empty())
    {
        result += nums.top();
        nums.pop();
    }
    return result;
}
